#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;

struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {};
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {};
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {};
};

class Solution
{
private:
	// 617. Merge two binary trees
	TreeNode *mergeTrees(TreeNode *root1, TreeNode *root2)
	{
		TreeNode *root = new TreeNode(0);
		if (!root1 && !root2)
			return nullptr;
		else if (!root1 && root2)
		{
			root->val = root2->val;
			root->left = root2->left;
			root->right = root2->right;
		}
		else if (root1 && !root2)
		{
			root->val = root1->val;
			root->left = root1->left;
			root->right = root1->right;
		}
		else
		{
			root->val = root1->val + root2->val;
			root->left = mergeTrees(root1->left, root2->left);
			root->right = mergeTrees(root1->right, root2->right);
		}
		return root;
	}

	// 637. Average of levels in binary tree
	vector<double> averageOfLevels(TreeNode *root)
	{
		queue<TreeNode *> q;
		q.push(root);

		vector<double> res;
		TreeNode *cur;
		double n, level_sum = 0;
		while (!q.empty())
		{
			n = q.size();
			for (int i = 0; i < n; i++)
			{
				cur = q.front();
				q.pop();
				level_sum += cur->val;
				if (cur->left)
					q.push(cur->left);
				if (cur->right)
					q.push(cur->right);
			}
			res.push_back(level_sum / n);
			level_sum = 0;
		}
		return res;
	}

	// Preorder traversal helper
	void PreOrder(TreeNode *root, vector<int> &nums)
	{
		if (!root)
			return;
		nums.push_back(root->val);
		PreOrder(root->left, nums);
		PreOrder(root->right, nums);
	}

	// 653. Two sum in BST
	bool findTarget(TreeNode *root, int k)
	{
		vector<int> nums;
		PreOrder(root, nums);

		unordered_map<int, int> map;
		for (int i = 0; i < nums.size(); i++)
		{
			if (map[k - nums[i]] == 1)
				return true;
			map[nums[i]] = 1;
		}
		return false;
	}

	// 671. Second minimum node in BST
	int findSecondMinimumValue(TreeNode *root)
	{
		if (!root || !root->left || !root->right)
			return -1;
		int l = findSecondMinimumValue(root->left);
		int r = findSecondMinimumValue(root->right);
		if (root->left->val == root->right->val)
		{
			if (l == -1 && r != -1)
				return r;
			if (l != -1 && r == -1)
				return l;
			if (l == -1 && r == -1)
				return -1;
			return min(l, r);
		}
		else if (root->left->val < root->right->val)
		{
			if (l == -1)
				return root->right->val;
			return min(l, root->right->val);
		}
		else if (root->left->val > root->right->val)
		{
			if (r == -1)
				return root->left->val;
			return min(r, root->left->val);
		}
		return -1;
	}

	// 700. Search in BST
	TreeNode *searchBST(TreeNode *root, int val)
	{
		queue<TreeNode *> q;
		q.push(root);
		TreeNode *cur;
		while (!q.empty())
		{
			cur = q.front();
			q.pop();
			if (cur->val == val)
				return cur;
			if (cur->left)
				q.push(cur->left);
			if (cur->right)
				q.push(cur->right);
		}
		return nullptr;
	}

	// 783. Minimum difference in BST
	int minDiffInBST(TreeNode *root)
	{
		queue<TreeNode *> q;
		q.push(root);
		vector<int> arr;
		TreeNode *cur;
		while (!q.empty())
		{
			cur = q.front();
			q.pop();
			arr.push_back(cur->val);
			if (cur->left)
				q.push(cur->left);
			if (cur->right)
				q.push(cur->right);
		}
		sort(arr.begin(), arr.end());
		int res = INT_MAX;
		for (int i = 1; i < arr.size(); i++)
			res = min(res, arr[i] - arr[i - 1]);
		return res;
	}

	// Helper for leaf nodes
	void inorder(TreeNode *root, vector<int> &arr)
	{
		if (!root)
			return;
		inorder(root->left, arr);
		if (!root->left && !root->right)
			arr.push_back(root->val);
		inorder(root->right, arr);
	}

	// 872. Leaf-similar trees
	bool leafSimilar(TreeNode *root1, TreeNode *root2)
	{
		vector<int> arr1, arr2;
		inorder(root1, arr1);
		inorder(root2, arr2);
		if (arr1.size() != arr2.size())
			return false;
		for (int i = 0; i < arr1.size(); i++)
		{
			if (arr1[i] != arr2[i])
				return false;
		}
		return true;
	}

	// Helper for increasingBST
	void inorder(TreeNode *node, TreeNode *&cur)
	{
		if (!node)
			return;
		inorder(node->left, cur);
		cur->right = new TreeNode(node->val); // Create new node
		cur = cur->right;
		inorder(node->right, cur);
	}

	// 897. Increasing order search tree
	TreeNode *increasingBST(TreeNode *root)
	{
		TreeNode *dummy = new TreeNode(0);
		TreeNode *cur = dummy;
		inorder(root, cur);
		return dummy->right;
	}

	// 938. Range sum of BST
	int rangeSumBST(TreeNode *root, int low, int high)
	{
		queue<TreeNode *> q;
		q.push(root);
		int res = 0;
		TreeNode *cur;
		while (!q.empty())
		{
			cur = q.front();
			q.pop();
			if (cur->val >= low && cur->val <= high)
				res += cur->val;
			if (cur->left)
				q.push(cur->left);
			if (cur->right)
				q.push(cur->right);
		}
		return res;
	}

	// 965. Check univalued tree
	bool isUnivalTree(TreeNode *root)
	{
		queue<TreeNode *> q;
		q.push(root);
		TreeNode *cur;
		while (!q.empty())
		{
			cur = q.front();
			q.pop();
			if (cur->val != root->val)
				return false;
			if (cur->left)
				q.push(cur->left);
			if (cur->right)
				q.push(cur->right);
		}
		return true;
	}

	// 1022. Sum of root-to-leaf binary numbers
	int dfs(TreeNode *root, int cur)
	{
		if (!root)
			return 0;
		cur = (cur << 1) | root->val; // Update binary number
		if (!root->left && !root->right)
			return cur;
		return dfs(root->left, cur) + dfs(root->right, cur);
	}
	int sumRootToLeaf(TreeNode *root)
	{
		return dfs(root, 0);
	}
};

// 703. Kth largest element in stream
class KthLargest
{
public:
	priority_queue<int, vector<int>, greater<int>> pq; // Min-heap
	int kk;

	KthLargest(int k, vector<int> &nums)
	{
		kk = k;
		for (int x : nums)
			add(x);
	}

	int add(int val)
	{
		if (pq.size() < kk)
			pq.push(val);
		else if (val > pq.top())
		{
			pq.pop();
			pq.push(val);
		}
		return pq.top();
	}
};

/**
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */
